package main.leetcode.clockin.May;

/**
 * 4.寻找两个正序数组的中位数
 *
 * <p>给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 *
 * <p>请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 *
 * <p>你可以假设 nums1 和 nums2 不会同时为空。
 *
 * <p>
 *
 * <p>示例 1: nums1 = [1, 3] nums2 = [2]
 *
 * <p>则中位数是 2.0
 *
 * <p>示例 2: nums1 = [1, 2] nums2 = [3, 4]
 *
 * <p>则中位数是 (2 + 3)/2 = 2.5
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day24 {
    public static void main(String[] args) {
        System.out.println(new day24().findMedianSortedArrays(new int[] {1, 3}, new int[] {2}));
        System.out.println(new day24().findMedianSortedArrays(new int[] {1, 2}, new int[] {3, 4}));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] tmp = new int[m + n];
        int i = 0, j = 0;
        for (int k = 0; k < m + n; ++k) {
            if (i >= m) {
                tmp[k] = nums2[j++];
            } else if (j >= n) {
                tmp[k] = nums1[i++];
            } else {
                tmp[k] = nums1[i] > nums2[j] ? nums2[j++] : nums1[i++];
            }
        }
        return (m + n & 1) == 0
                ? (double) (tmp[m + n >>> 1] + tmp[(m + n >>> 1) - 1]) / 2
                : tmp[m + n >>> 1];
    }
}
